package com.adee.algorithm.structure;

import java.util.*;

/**
 * 动态规划
 */
public class Test006_DynamicProgram {
    public static void main(String[] args) {
        System.out.println(feibonaqi(1));
        System.out.println(feibonaqi(2));
        System.out.println(feibonaqi(3));
        System.out.println(feibonaqi(4));
        System.out.println(feibonaqi(5));
        System.out.println(feibonaqi(6));

        long m = System.currentTimeMillis();
        System.out.println(tiaotaijie(42));
        long m1 = System.currentTimeMillis();
        System.out.println("暴力递归耗时：" + (m1-m));
        System.out.println(tiaotaijie2(42));
        long m2 = System.currentTimeMillis();
        System.out.println("记忆搜索耗时：" + (m2-m1));
        System.out.println(tiaotaijie3(42));
        long m3 = System.currentTimeMillis();
        System.out.println("递推耗时：" + (m3-m2));

        // childSerial(new int[]{186, 186, 150, 200, 160, 130, 197, 200});

        // dadaoafu(null, 1);

        lcs();

        String s1 = "abcde28ccdff";
        String s2 = "bcd328ccddfff";
        commonStr(s1, s2);

        maxChildSerial();

        bag();

        longestCommonSubsequence5Test();

    }

    // 斐波那契数列 ，求第n个位置的数值
    public static int feibonaqi(int n) {
        if (n == 0 || n == 1) return 1;
        int[] dp = new int[n+1];
        dp[0] = 1;
        dp[1] = 1;
        for (int i = 2; i <= n; i++) {
            dp[i] = dp[i-1] + dp[i-2];
        }
        return dp[n];
    }

    /**
     * 跳台阶
     * 每次可以跳1或2层，求跳到第n层共有多少种跳法。（层数从1开始）
     * 解法：跳到第n层有k(n)种跳法，只存在两种情况，从n-1跳过来或从n-2跳过来，所以共有k(n-1)+k(n-2)种跳法。
     * 类似于斐波那契数列，递推实现
     */
    // 解法1：暴力求解，递归树中存在重复子树，时间复杂度为O(2^n)，n较大时非常耗时
    public static int tiaotaijie(int n) {
        if (n == 1) return 1;
        if (n == 2) return 2;
        return tiaotaijie(n-1) + tiaotaijie(n-2);
    }

    // 解法2：对暴力求解优化，是用一个记忆数组，避免重复子树重复递归计算
    public static int tiaotaijie2(int n) {
        int[] mem = new int[n+1];
        return doTiaotaijie2(mem, n);
    }
    public static int doTiaotaijie2(int[] mem, int n) {
        if (mem[n] > 0) return mem[n];
        int sum = 0;
        if (n == 1) return 1;
        if (n == 2) return 2;
        sum = doTiaotaijie2(mem, n-1) + doTiaotaijie2(mem,n-2);
        mem[n] = sum;
        return sum;
    }

    // 解法3：递推公式，自底向上求解，递推公式为：k(n-1)+k(n-2)->k(n)。递归是自顶向下。
    public static int tiaotaijie3(int n) {
        int kn_2 = 1;
        int kn_1 = 2;
        for (int i = 3; i <= n; i++) {
            int tmp = kn_1;
            kn_1 = kn_1 + kn_2;
            kn_2 = tmp;
        }
        return kn_1;
    }


    /**
     * 大盗阿福：阿福偷东西，如果偷一家商店，则相邻两家不能偷，否则报警系统触发，
     * 每个店都有不同金额的现金，共有n个店，求阿福最多能偷多少钱。
     * 动态规划问题：num[n]保存每家店的现金额，sum[n]表示n家店最大可偷钱数。
     * 寻找递推公式：
     * sum[1] = num[1];
     * sum[2] = max(num[1],num[2]);
     * sum[3] = max(sum[2],sum[1]+num[3]);
     * ...
     * sum[n] = max(sum[n-1],sum[n-2]+num[n]);
     */
    public static void dadaoafu(int[] num, int n) {
        num = new int[]{1,8,2};
        n = 3;
        System.out.println(doDadaoafu(num, n-1));

        num = new int[]{10,7,6,14};
        n = 4;
        System.out.println(doDadaoafu(num, n-1));


        num = new int[44];
        for (int i = 0; i < 40; i++) {
            num[i] = new Random().nextInt(200);
        }
        n = num.length;
        int[] dp = new int[num.length];

        long m = System.currentTimeMillis();
        System.out.println(doDadaoafu(num, n-1));
        long m1 = System.currentTimeMillis();
        System.out.println("暴力递归耗时：" + (m1-m));
        System.out.println(doDadaoafu2(dp, num, n-1));
        long m2 = System.currentTimeMillis();
        System.out.println("记忆搜索耗时：" + (m2-m1));
        System.out.println(doDadaoafu3(num, n));
        long m3 = System.currentTimeMillis();
        System.out.println("递推耗时：" + (m3-m2));

    }
    // 递推公式-递归实现
    public static int doDadaoafu(int[] num, int n) {
        if (n == 0) return num[0];
        if (n == 1) return Integer.max(num[0], num[1]);
        return Integer.max(doDadaoafu(num, n-1), doDadaoafu(num, n-2)+num[n]);
    }
    // 递归优化-记忆搜索
    public static int doDadaoafu2(int[] dp, int[] num, int n) {
        if (dp[n] > 0) return dp[n];
        if (n == 0) return num[0];
        if (n == 1) return Integer.max(num[0], num[1]);
        int ret = Integer.max(doDadaoafu2(dp, num, n-1), doDadaoafu2(dp, num, n-2)+num[n]);
        dp[n] = ret;
        return ret;
    }
    // 递推公式
    public static int doDadaoafu3(int[] num, int n) {
        int sumn_2 = num[0];
        int sumn_1 = Integer.max(num[0], num[1]);
        for (int i = 2; i < n; i++) {
            int tmp = sumn_1;
            sumn_1 = Integer.max(sumn_1, sumn_2+num[i]);
            sumn_2 = tmp;
        }
        return sumn_1;
    }


    // 最长公共子序列
    // ai 起始下标，aj 终止下标
    public static void lcs() {
//        int[] a = {1,3,4,5,6,7,7,8,9,1,6,2,7,3,6,1,4,0,4,9,1,3,0,5,1,6,8,5};
//        int[] b = {3,5,7,4,8,6,7,8,2,1,9,2,6,5,0,7,3,2,8,4,6,0,7,1};
        int[] a = {1,3,4,5,6,7,7,8,9,1,6,2,7,3};
        int[] b = {3,5,7,4,8,6,7,8,2,1,9,2,6,5,0,7,3,2,8,4,6,0,7,1};

        System.out.println("hell" + 'w');
        String text1 = "ylqpejqbalahwr";
        String text2 = "yrkzavgdmdgtqpg";

        long m = System.currentTimeMillis();
//        print(doLcs(a,b));
        System.out.println(longestCommonSubsequence(text1,text2));
        long m1 = System.currentTimeMillis();
        System.out.println("暴力递归耗时：" + (m1-m));

        int[][][] bp = new int[a.length+1][b.length+1][];
//        print(doLcs2(bp,a,b));
        System.out.println(longestCommonSubsequence2(text1,text2));
        long m2 = System.currentTimeMillis();
        System.out.println("记忆搜索耗时：" + (m2-m1));

        System.out.println(longestCommonSubsequence3(text1,text2));
        long m3 = System.currentTimeMillis();
        System.out.println("递推公式耗时：" + (m3-m2));
        System.out.println("最长子序列：" + longestCommonSubsequence4(text1,text2));
        long m4 = System.currentTimeMillis();
        System.out.println("耗时：" + (m4-m3));

    }
    // 暴力递归
    public static int[] doLcs(int[] a, int[] b) {
        if (a.length == 0 || b.length == 0) return new int[0];
        int[] an_1 = Arrays.copyOfRange(a, 0,a.length-1);
        int[] bn_1 = Arrays.copyOfRange(b, 0,b.length-1);
        if (a[a.length-1] == b[b.length-1]) {
            int[] arr = doLcs(an_1, bn_1);
            int[] ret = new int[arr.length+1];
            System.arraycopy(arr, 0, ret, 0, arr.length);
            ret[arr.length] = a[a.length-1];
            return ret;
        }else {
            int[] ret1 = doLcs(an_1, b);
            int[] ret2 = doLcs(a, bn_1);
            return ret1.length >= ret2.length ? ret1 : ret2;
        }
    }
    // 记忆搜索 - 递归优化
    public static int[] doLcs2(int[][][] bp, int[] a, int[] b) {
        if (bp[a.length][b.length] != null) return bp[a.length][b.length];
        if (a.length == 0 || b.length == 0) return new int[0];
        int[] an_1 = Arrays.copyOfRange(a, 0,a.length-1);
        int[] bn_1 = Arrays.copyOfRange(b, 0,b.length-1);
        int[] ret;
        if (a[a.length-1] == b[b.length-1]) {
            int[] arr = doLcs(an_1, bn_1);
            ret = new int[arr.length+1];
            System.arraycopy(arr, 0, ret, 0, arr.length);
            ret[arr.length] = a[a.length-1];
        }else {
            int[] ret1 = doLcs(an_1, b);
            int[] ret2 = doLcs(a, bn_1);
            ret = ret1.length >= ret2.length ? ret1 : ret2;

        }
        bp[a.length][b.length] = ret;
        return ret;
    }

    // 最长公共子序列 - 暴力递归 - 超时
    public static int longestCommonSubsequence(String text1, String text2) {
        if(text1.length() == 0|| text2.length() == 0) {
            return 0;
        }
        String s1 = text1.substring(0,text1.length()-1);
        String s2 = text2.substring(0,text2.length()-1);
        if (text1.charAt(text1.length()-1) == text2.charAt(text2.length()-1)) {
            return longestCommonSubsequence(s1,s2)+1;
        }else{
            return Integer.max(longestCommonSubsequence(s1, text2),longestCommonSubsequence(text1, s2));
        }
    }

    // 最长公共子序列 - 记忆搜索 - 超时
    public static int longestCommonSubsequence2(String text1, String text2) {
        int[][] bp = new int[text1.length()+1][text2.length()+1];
        return doLongestCommonSubsequence2(bp,text1,text2);
    }
    public static int doLongestCommonSubsequence2(int[][] bp, String text1, String text2) {
        if(text1.length() == 0|| text2.length() == 0) {
            return 0;
        }
        int ret;
        String s1 = text1.substring(0,text1.length()-1);
        String s2 = text2.substring(0,text2.length()-1);
        if (text1.charAt(text1.length()-1) == text2.charAt(text2.length()-1)) {
            ret = longestCommonSubsequence(s1,s2)+1;
        }else{
            ret = Integer.max(longestCommonSubsequence(s1, text2),longestCommonSubsequence(text1, s2));
        }
        bp[text1.length()][text2.length()] = ret;
        return ret;
    }

    // 最长公共子序列长度 - 递推公式
    /**
     * 递推公式如下：
     *
     * dp[i][j] =   dp[i−1][j−1]+1                 text1[i−1] = text2[j−1]
     *              max(dp[i−1][j],dp[i][j−1])     text1[i−1] <> text2[j−1]
     */
    public static int longestCommonSubsequence3(String text1, String text2) {
        int len1 = text1.length();
        int len2 = text2.length();
        int[][] bp = new int[len1+1][len2+1];
        for (int i = 0; i <= len1; i++) {
            bp[i][0] = 0;
        }
        for (int i = 0; i <= len2; i++) {
            bp[0][i] = 0;
        }
        for (int i = 1; i <= len1; i++) {
            for (int j = 1; j <= len2; j++) {
                if(text1.charAt(i-1) == text2.charAt(j-1)) {
                    bp[i][j] = bp[i-1][j-1] + 1;
                }else {
                    bp[i][j] = Integer.max(bp[i-1][j], bp[i][j-1]);
                }
            }
        }
        return bp[len1][len2];
    }



    // 最长公共子序列 - 递推公式
    /**
     * 递推公式如下：
     *
     * dp[i][j] =   dp[i−1][j−1]+1                 text1[i−1] = text2[j−1]
     *              max(dp[i−1][j],dp[i][j−1])     text1[i−1] <> text2[j−1]
     */
    public static String longestCommonSubsequence4(String text1, String text2) {
        int len1 = text1.length();
        int len2 = text2.length();
        String[][] bp = new String[len1+1][len2+1];
        for (int i = 0; i <= len1; i++) {
            bp[i][0] = "";
        }
        for (int i = 0; i <= len2; i++) {
            bp[0][i] = "";
        }
        for (int i = 1; i <= len1; i++) {
            for (int j = 1; j <= len2; j++) {
                if(text1.charAt(i-1) == text2.charAt(j-1)) {
                    bp[i][j] = bp[i-1][j-1] + text1.charAt(i-1);
                }else {
                    bp[i][j] = bp[i-1][j].length() >= bp[i][j-1].length() ? bp[i-1][j] : bp[i][j-1];
                }
            }
        }
        return bp[len1][len2];
    }

    public static int[] longestCommonSubsequence5(int[] a, int[] b) {
        int[][][] dp = new int[a.length+1][b.length+1][];
        for (int i = 0; i <= a.length; i++) {
            dp[i][0] = new int[0];
        }
        for (int i = 0; i <= b.length; i++) {
            dp[0][i] = new int[0];
        }
        for (int i = 1; i <= a.length; i++) {
            if (i-2 >= 0) {
                for (int j = 0; j < b.length; j++) {
                    dp[i-2][j] = null;
                }
            }
            for (int j = 1; j <= b.length; j++) {
                if (j-2 >= 0) {
                    dp[i][j-2] = null;
                }
                if (a[i-1] == b[j-1]) {
                    int[] tmp = new int[dp[i-1][j-1].length+1];
                    System.arraycopy(dp[i-1][j-1],0,tmp,0,tmp.length-1);
                    tmp[tmp.length-1] = a[i-1];
                    dp[i][j] = tmp;
                }else {
                    int[] t1 = dp[i-1][j];
                    int[] t2 = dp[i][j-1];
                    if (t1.length > t2.length) {
                        dp[i][j] = Arrays.copyOfRange(t1,0,t1.length);
                    }else if(t1.length == t2.length) {
                        int[] t = dicPrimary(t1,t2);
                        dp[i][j] = Arrays.copyOfRange(t,0,t.length);
                    }else {
                        dp[i][j] = Arrays.copyOfRange(t2,0,t2.length);
                    }
                }
            }
        }
        return dp[a.length][b.length];
    }

    public static void longestCommonSubsequence5Test() {
        int[] arr = {3,8,1,2,9,};
        Arrays.sort(arr);
        print(arr);
    }


    /**
     * 最长公共子串，与最长公共子序列不同的是，递推关系从前往后考虑比较容易理解
     *
     * bp[i][j] 从前向后，表示s1中长度为i的子串与s2中长度为j的子串，二者以其最后一个字符结尾的公共子串的长度，
     *
     * 注意，用递归解不出来，需要用递推公式正向求解。
     */
    public static void commonStr(String s1, String s2) {
        int[][] bp = new int[s1.length()+1][s2.length()+1];
        for (int i = 0; i <= s1.length(); i++) {
            bp[i][0] = 0;
        }
        for (int i = 0; i <= s2.length(); i++) {
            bp[0][i] = 0;
        }
        int maxLen = 0;
        int maxLenIdx = 0;
        for (int i = 1; i <= s1.length(); i++) {
            for (int j = 1; j <= s2.length(); j++) {
                if (s1.charAt(i-1) == s2.charAt(j-1)) {
                    bp[i][j] = bp[i-1][j-1] + 1;
                }else {
                    bp[i][j] = 0;
                }
                if (bp[i][j] > maxLen) {
                    maxLen = bp[i][j];
                    maxLenIdx = i-1;
                }
            }
        }
        System.out.printf("最长公共子串：[%d] %s\n", maxLen, s1.substring(maxLenIdx+1-maxLen, maxLenIdx+1));
    }

    /**
     * 最长递增子序列
     * n个数的序列：nums[n]
     * dp[i]表示以nums[i]结尾的递增子序列的最大长度
     * 递推公式： foreach  0 <= j < i
     *          if(nums[i] > nums[j]) dp[i] = max(dp[i], dp[j] + 1)
     */
    public static void maxChildSerial() {
        int[] nums = {2, 1, 5, 3, 6, 4, 8, 9, 7};
        System.out.println("原序列：");
        print(nums);
        int[] dp = new int[nums.length];
        Arrays.fill(dp, 1);
        int max = 1;
        for (int i = 1; i < nums.length; i++) {
            for (int j = 0; j < i; j++) {
                if (nums[i] > nums[j]) {
                    dp[i] = Integer.max(dp[i], dp[j]+1);
                }
            }
            if (dp[i] > max) max = dp[i];
        }
        System.out.println("最长递增子序列长度：" + max);
    }

    /**
     * 背包问题
     * 有n个物品，v[i]为第i个物品的价值，w[i]为第i个物品的重量，
     * 背包最大能承受重量为x，求解背包能容纳的最大价值。
     *
     * bp[i][j] 代表的是前 i 个物品加入容量为 j 的背包里面价值总和的最大值
     * 每个物品都有“选”和“不选”两种情况，
     * 情况1：不选i，bp[i][j] = bp[i-1][j]
     * 情况2：选i，bp[i][j] = bp[i-1][j-w[i]] + v[i]
     *
     * 直接采用递推公式：bp[i][j] = max(bp[i-1][j],bp[i-1][j-w[i]] + v[i])
     */
    public static void bag() {
        int x = 10;
        int[] v = {8,10,4,5,5};
        int[] w = {6,4,2,4,3};
        int[][] bp = new int[v.length+1][x+1];
        for (int i = 0; i <= v.length; i++) {
            bp[i][0] = 0;
        }
        for (int i = 0; i <= x; i++) {
            bp[0][i] = 0;
        }
        for (int i = 1; i <= v.length; i++) {
            for (int j = 1; j <= x; j++) {
                if (j-w[i-1] >= 0) {
                    bp[i][j] = Integer.max(bp[i-1][j],bp[i-1][j-w[i-1]] + v[i-1]);
                }else {
                    bp[i][j] = bp[i-1][j];
                }
            }
        }
        System.out.println(bp[v.length][x]);
    }




    // 升序排列 最长子序列 - 暴力求解
    public static void childSerial(int[] arr) {
        print(arr);
        int len = arr.length;
        List<Integer> retList = null;
        for (int i = 0; i < len; i++) {
            List<Integer> list = new ArrayList<>(len);
            list.add(arr[i]);
            for (int j = i+1; j < len; j++) {
                if (list.get(list.size()-1) < arr[j]) {
                    list.add(arr[j]);
                }
            }
            if(retList == null || list.size() > retList.size()) {
                retList = list;
            }
        }
        print(retList);
    }

    // 按字典顺序比较
    private static int[] dicPrimary(int[] a, int[] b) {
        for (int i = 0; i < a.length; i++) {
            if (a[i] < b[i]) {
                return a;
            }else if (a[i] > b[i]) {
                return b;
            }
        }
        return a;
    }

    static void print(int[] arr) {
        if (arr == null || arr.length == 0) return;
        for (int i : arr) {
            System.out.print(i + " ");
        }
        System.out.println();
    }

    static void print(List<Integer> list) {
        list.forEach(i -> { System.out.print(i + " "); });
        System.out.println();
    }

}
